package leetcode.sort;

import leetcode.util.CommonUtils;
import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

import java.util.*;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author ：zsy
 * @date ：Created 2021/10/23 22:37
 * @description：
 */
public class Test1 {

    int[] nums = {2, 4, 5, 6, 8, 9, 10, 1, 3, 7};

    public static void main(String[] args) {
        Stack stack = new Stack();

   }
    @Test
    public void quick_sort_test() {
        quick_sort(nums, 0, nums.length - 1);
        System.out.println("快排：" + Arrays.toString(nums));
    }

    public void quick_sort(int[] arr, int left, int right) {
        if (left >= right) return;
        int l = left;
        int r = right;
        int mid = arr[l];
        while (l < r) {
            while (l < r && arr[r] >= mid) r--;
            arr[l] = arr[r];
            while (l < r && arr[l] <= mid) l++;
            arr[r] = arr[l];
        }
        arr[l] = mid;
        quick_sort(arr, left, l - 1);
        quick_sort(arr, l + 1, right);
    }

    @Test
    public void heap_sort_test() {
        heap_sort(nums);
        System.out.println("堆排：" + Arrays.toString(nums));
    }

    public void heap_sort(int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            adjust(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            CommonUtils.charge(arr, i, 0);
            adjust(arr, 0, i);
        }
    }

    /**
     * 构建大顶堆
     * @param arr
     * @param parentIndex
     * @param len
     */
    public void adjust(int[] arr, int parentIndex, int len) {
        int temp = arr[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < len) {
            if (childIndex + 1 < len && arr[childIndex + 1] > arr[childIndex]) childIndex++;
            if (arr[childIndex] < temp) break;
            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        arr[parentIndex] = temp;
    }

    @Test
    public void bubble_sort_test() {
        bubble_sort(nums);
        System.out.println("冒泡：" + Arrays.toString(nums));
    }

    /**
     * 2 4 9 3 5 7
     *
     * @param arr
     */
    public void bubble_sort(int[] arr) {
        boolean flag;
        for (int i = 0; i < arr.length; i++) {
            flag = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    CommonUtils.charge(arr, j + 1, j);
                    flag = false;
                }
            }
            if (flag) break;
        }
    }

    @Test
    public void select_sort_test() {
        select_sort(nums);
        System.out.println("选择：" + Arrays.toString(nums));
    }

    /**
     *
     * @param arr
     */
    public void select_sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            CommonUtils.charge(arr, minIndex, i);
        }
    }

    @Test
    public void merge_sort_test() {
        merge_sort(nums, 0, nums.length - 1, new int[nums.length]);
        System.out.println("归并：" + Arrays.toString(nums));
    }

    public void merge_sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + right >> 1;
            merge_sort(arr, left, mid, temp);
            merge_sort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid || j <= right) {
            temp[t++] = (i <= mid ? arr[i] : Integer.MAX_VALUE)
                    < (j <= right ? arr[j] : Integer.MAX_VALUE) ? arr[i++] : arr[j++];
        }
        int tempLeft = left;
        t = 0;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }
    }

    @Test
    public void insert_sort_test() {
        insert_sort(nums);
        System.out.println("插入：" + Arrays.toString(nums));
    }

    public void insert_sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertIndex = i - 1;
            int insertValue = arr[i];
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertValue;
            }
        }
    }

    @Test
    public void printABC() throws InterruptedException {
        Data data = new Data();
        new Thread(() -> {
            for (int i = 0; i < 10; i++)
                data.printA();
        }).start();
        new Thread(() -> {
            for (int i = 0; i < 10; i++)
                data.printB();
        }).start();
        new Thread(() -> {
            for (int i = 0; i < 10; i++)
                data.printC();
        }).start();
        TimeUnit.SECONDS.sleep(1);
    }

    class Data {
        private int num = 1;
        ReentrantLock lock = new ReentrantLock();
        Condition conditionA = lock.newCondition();
        Condition conditionB = lock.newCondition();
        Condition conditionC = lock.newCondition();

        private void printA() {
            lock.lock();
            try {
                if (num != 1) {
                    conditionA.await();
                }
                System.out.print('A');
                num = 2;
                conditionB.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }

        private void printB() {
            lock.lock();
            try {
                if (num != 2) {
                    conditionB.await();
                }
                System.out.print('B');
                num = 3;
                conditionC.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }

        private void printC() {
            lock.lock();
            try {
                if (num != 3) {
                    conditionC.await();
                }
                System.out.println('C');
                num = 1;
                conditionA.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    }

    @Test
    public void lru_cache_test() {
        LRUCache<Integer, Integer> lruCache = new LRUCache<>(3);
        lruCache.put(1,2);
        lruCache.put(2,2);
        lruCache.put(3,2);
        lruCache.get(2);
        //必须这样测试
        //否则会报ConcurrentModificationException异常
        Iterator<Map.Entry<Integer, Integer>> it = lruCache.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry entry = it.next();
            System.out.println(entry.getKey() + "   " + entry.getValue());
        }
        lruCache.put(4,3);
        lruCache.get(2);
        lruCache.put(4,5);
        it = lruCache.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry entry = it.next();
            System.out.println(entry.getKey() + "   " + entry.getValue());
        }
    }

    class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private final int CACHE_SIZE;

        public LRUCache(int cache_size) {
            super((int)Math.ceil(cache_size / 0.75) + 1, 075f, true);
            this.CACHE_SIZE = cache_size;
        }

        @Override
        public boolean removeEldestEntry(Map.Entry<K, V> entry) {
            return size() > this.CACHE_SIZE;
        }
    }

    @Test
    public void BFS_tree() {
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
        //bfs(root);
        infix_order(root);
    }

    public void bfs(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                System.out.println(cur);
            }
        }
    }

    public void infix_order(TreeNode root) {
        if (root != null)
            System.out.println(root);
        infix_order(root.left);
        infix_order(root.right);
    }
}
